Quiz (Week 1)

Haskell's built-in string type String is actually just a type synonym for a list of characters [Char]. Thus, Answer 2 is correct. String was not a choice, but would also have been a correct answer. The names of types (like Char or Bool) are always written with initial upper-case letters: string is not a Haskell type, so Answer 3 is not correct.

In Haskell, a tuple (x,y) is typed according to the following typing rule:

This can be read as follows: (x,y) has type \((\tau_1, \tau_2)\) if x has type \(\tau_1\) and y has type \(\tau_2\).

A similar rule exists for triples like (255,'x',[True, False]). Since 255 has type Int, 'x' has type Char, and the list of boolean values, [True, False] has type [Bool], we get that Answer 1 is the only correct answer.

Keeping in mind that String is a synonym for [Char], we have the type of cons (the (:) operator) as:

(:) :: a -> [a] -> [a]

If we apply the first argument, "world":

("world":) :: [[Char]] -> [[Char]]

Once we apply the second argument, [], we have:

("world":[]) :: [[Char]]

The whole tuple has type

("hello", "world":[]) :: ([Char], [[Char]])

and the snd function has type

snd :: (a,b) -> b

Therefore, applying the snd function to the tuple yields [[Char]]. The answer is number 1.

It's worth noting that all functions in Haskell accept one argument and return one result. Multi-argument functions are emulated by writing a function that, given its first argument, returns a function that awaits further arguments. This technique is called currying.

For example, the function map has the following type:

map :: (a -> b) -> [a] -> [b]

This can be more explicitly expressed with the right-associated parentheses, as follows:

map :: (a -> b) -> ([a] -> [b])

Given the argument function (\x -> x + 1), a lambda expression of type Int -> Int, map shall return a function of type [Int] -> [Int], or option 3.

The code snippet first reverses the string "hello", then concatenates it with the string "world". Therefore, only options 1 and 2 are correct parenthesizations. The 3rd option evaluates to a different result (what?) and the 4th option does not even type-check (why?).

As discussed in the lecture, the function type constructor -> is right-associative, so answers 1 and 3 are correct. Answer 2 is not correct since the types (a -> b) -> c and a -> (b -> c) are always different. Answer 4 is not correct either: square brackets denote list types, so Answer 4 is the type of a function that takes an input of type a, and returns a list of functions, each of type b -> c -> a, as output.

The following bit of equational reasoning hits every answer in this question, except 4, which is not type correct.

let increment x = 1 + x
in \xs -> map chr (map increment (map ord xs))
= -- Shift argument into lambda
let increment = \x -> 1 + x
in \xs -> map chr (map increment (map ord xs))
= -- Simplify lambda to operator section
let increment = (1 +)
in \xs -> map chr (map increment (map ord xs))
= -- Reduce let expression by substitution 
\xs -> map chr (map (1 +) (map ord xs))
= -- Introduce composition, f (g x) = (f . g) x
\xs -> (map chr . map (1 +)) (map ord xs))
= -- Remove parentheses with ($)
\xs -> map chr . map (1 +) $ map ord xs -- Answer 5
= -- Introduce further composition: f $ g x = (f . g) x
\xs -> (map chr . map (1 +) . map ord) xs
= -- η-reduction
map chr . map (1 +) . map ord -- Answer 1
= -- Map (functor) law, map f . map g = map (f . g)
map (chr . (1 +) . ord) -- Answer 2
= -- succ is defined for Char values as chr . (1 +) . ord
map succ -- Answer 3

The following derivation shows the equivalence to answers 1 and 2.

foldr (&&) True . map (>=0)
= -- and = foldr (&&) True
and . map (>=0) -- Answer 1
= -- all f = and . map f
all (>=0) -- Answer 2

Furthermore, Answer 4 is also equivalent, as the following derivation shows:

foldr (&&) True . map (>=0)
= -- η-expansion on the (&&)
foldr (\a b -> a && b) True . map (>=0)
= -- We have a fold/map rule
  -- foldr (\x y -> z) . map f = foldr (\x y -> z[x := f x])
  -- (where z[x:=f x] is a substitution).
foldr (\a b -> (>= 0) a && b) True
= -- Nicer syntax
foldr (\a b -> a >= 0 && b) True -- Answer 4